import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

import java.util.Stack;

public class MySort {

    private static void swap(int[] array , int x , int y){
        int tmp = array[x] ;
        array[x] = array[y] ;
        array[y] = tmp ;
    }
//    public static void quickSort(int[] array){
//        quick(array , 0 , array.length-1);
//    }
//
//    public static void insertSort(int[] arr , int start , int end) {
//        for (int i = start + 1; i <= end; i++) {
//            int tmp = arr[i];
//            int j = i - 1;
//            for (; j >= start; j--) {
//                if (arr[j] > tmp) {
//                    arr[j + 1] = arr[j];
//                } else {
//                    //arr[j+1] = tmp ;
//                    break;
//                }
//            }
//            arr[j + 1] = tmp;  //这里的arr[j+1] = tmp
//        }
//    }
//
//    private static void quick(int[] array , int start , int end){
//        if(start >= end) return ;
//       //  引入 直接插入在 剩余结点不多的时候，减少空间复杂度
//        if(start-end+1  < 15){
//             insertSort(array , start , end);
//             return;
//        }
//
//        //三数取中
//         int index = midOfThree(array , start , end);
//         //获得中间位置后交换key 和 中间数字
//         swap(array , index , start);
//
//        int pivot = partitionHoare(array , start , end);
//        quick(array , start , pivot-1);
//        quick(array , pivot+1 , end);
//
//
//    }
//     //三数取中方法
//    private static int midOfThree(int[] array, int left, int right) {
//        int mid  = (left + right) / 2 ;
//        if(array[left] < array[right]){
//            if(array[mid] < array[left]){
//                return left ;
//            }else if(array[mid] > array[right]){
//                return right ;
//            }else{
//                return mid ;
//            }
//        }else{
//            if(array[mid] > array[left]){
//                return left ;
//            }else if(array[mid] < array[right]){
//                return right ;
//            }else{
//                return mid ;
//            }
//        }
//        }
private static int partitionHoare(int[] array , int left , int right){
        int key = array[left] ;
        int tmp = left ;
        while(left < right){
            while (left < right && key <= array[right]){
                right -- ;
            }
            while (left < right && key >= array[left]){
                left ++ ;
            }
            swap(array , left , right);
        }
        swap(array , tmp , left);
        return left ;
    }
      public static void quickSortNor(int[] array){
         Stack<Integer> stack  =  new Stack<>();
         int left = 0 ;
         int right = array.length- 1 ;
         int pivot = partitionHoare(array,left,right);
         if(pivot-1 > left){
             stack.push(left) ;
             stack.push(pivot-1) ;
         }
         if(pivot+1 < right){
             stack.push(pivot+1);
             stack.push(right);
         }
         while(!stack.empty()){
             right = stack.pop();
             left = stack.pop() ;
              pivot = partitionHoare(array,left,right);
             if(pivot-1 > left){
                 stack.push(left) ;
                 stack.push(pivot-1) ;
             }
             if(pivot+1 < right){
                 stack.push(pivot+1);
                 stack.push(right);
             }
         }



      }



}
